Teoría combinatoria
La teoría combinatoria trata de las distintas formas de subgrupos que se pueden hacer dado un conjunto no vacío de elementos. Para la comprensión de toda situación combinatoria existen cuatro conceptos clave que se deben distinguir: población, muestra, orden y repetición.
Población: denotada por \(n\), es el cardinal del conjunto de elementos a estudiar.
Muestra: es un subconjunto de la población. Se denotará con la letra \(r\) al número de elementos que la componen. Los diferentes tipos de muestra vienen determinados por dos aspectos, orden y repetición.
Orden: si importa o no que los elementos de la muestra estén ordenados.
Repetición: la posibilidad de repetición o no de los elementos.
Para el estudio de la teoría combinatoria se hace necesario iniciar con el concepto matemático de factorial de un número natural \(n\). Por ahora, se define el factorial de un número natural \(n\) como el producto de los \(n\) factores consecutivos desde \(n\) hasta uno, denotado por \(n!\), lo cual se lee “ene factorial” $$n!=n\left(n-1\right)\left(n-2\right)\left(n-3\right)\ldots(6)(5)(4)(3)(2)(1)$$ de esta manera si se pide determinar \(6!\), se tiene: $$6!=6\times5\times4\times3\times2\times1=720$$ Donde, además se establece por definición el factorial de cero como \(0!=1=1!\) (convención fundamental para la coherencia en teoría combinatoria).
Otro elemento fundamental a considerar es llamado principio multiplicativo (también llamado principio fundamental de conteo), establece que si un primer evento \(E_1\) puede ocurrir de \(n\) formas, y luego un segundo evento \(E_2\) ocurre de m formas, la cantidad total de formas en que pueden ocurrir ambos eventos de manera sucesiva es el producto \(n\times m\). El principio es extensible a cualquier cantidad de eventos.
Ejemplo: Una cafetería escolar vende tres tipos de sándwiches de jamón y queso, los cuales varían en el tipo de pan (trigo, maíz y cebada). Además, ofrece cuatro tipos de bebidas saborizadas para acompañarlo (limón, naranja, maracuyá y cereza). Determinar de cuántas formas diferentes es posible elegir un sándwich y una bebida.
Solución: sea \(E_1\) el evento seleccionar el pan, entonces hay \(n=3\) formas para esto. Sea \(E_2\) el evento seleccionar la bebida, entonces hay \(m=4\) formas para \(E_2\). Aplicando el principio multiplicativo el total de maneras \(T\) en que es posible elegir es,
$$T=n\times m=3\times4=12$$
Clasificación de los posibles grupos.
Según entren o no todos los elementos de una población, importe o no el orden o se puedan repetir o no, los distintos grupos que se pueden realizar con los \(n\) elementos se clasifican en combinaciones, permutaciones y variaciones. Cada una de estas estudia por separado en una de las pestañas de arriba.
Para más contenidos y luego clic en la pestaña del contenido deseado.
Permutaciones.
Llamaremos permutación ordinaria de \(n\) elementos, lo cual denotaremos como \(P_n\), a los diferentes arreglos hechos con ellos tales que:
• Entran todos los elementos.
• Importa el orden
• No se repiten los elementos.
A partir de estas condiciones, para un conjunto de n elementos, es posible ordenarlos de forma tal que se tenga:
• \(n\) posibilidades para la primera posición.
• \(n-1\) posibilidades para la segunda posición.
• \(n-2\) posibilidades para la tercera posición, y así sucesivamente.
Al aplicar el principio multiplicativo para \(P_n\), el total de arreglos posibles es:
$$P_n=n\left(n-1\right)\left(n-2\right)\cdots\left(3\right)\left(2\right)\left(1\right)$$
y al notar que,
$$n\left(n-1\right)\left(n-2\right)\cdots\left(3\right)\left(2\right)\left(1\right)=n!$$
se escribe:
Permutaciones de \(n\) elementos
Ver Ejercicio I Ej1 y Ej2
Permutaciones circulares.
Son permutaciones en las cuales los elementos se ordenar "en círculo", (por ejemplo, los comensales en una mesa o jugadores de póker), de modo que el primer elemento que "se sitúe" en la muestra determina el principio y el final de muestra, de donde,
Permutaciones circulares de \(n\) elementos
Ver ejercicios I Ej3 y Ej4.
Permutaciones con reperición
Algunas veces al trabajar con permutaciones es posible repetir elementos, tales casos son llamados permutaciones con repetición de \(n\) elementos, donde \(n=a+b+c+\cdots+z\ldots\). Es estas, el primer elemento se repite \(a\) veces, el segundo \(b\) veces, y así sucesivamente. Los distintos arreglos para tales casos están dados por:
Permutaciones con repetición de \(n\) elementos
Las características de estas permutaciones son:
• Entran todos los elementos.
• Importa el orden
• Se repiten los elementos.
Ver Ejercicio I, Ej5, Ej6 y Ej7.
Para más contenidos y luego clic en la pestaña del contenido deseado.
Variaciones ordinarias.
En lo cotidiano una variación es una manera diferente de ordenar o realizar una determinada tarea. Llamaremos variaciones ordinarias, o simplemente variaciones, distintos arreglos de \(n\) elementos tomados de \(r\) en \(r\) donde \(n > r\), denotadas como \(V_n^r~~ {\rm o}~~ nPr\), tales que:
• No entran todos los elementos. \(n>r\).
• Importa el orden.
• No se repiten elementos.
Aunque estrictamente es posible el caso para \(n=r\), en tales situaciones diremos que es una permutación y no una variación. Al ordenar los \(n\) elementos de un conjunto tomados de \(r\) en \(r\), se tienen las siguientes posibilidades de elección:
• \(n\) elemetos para la primera posición.
• \(n-1\) elementos para la segunda posición, y así sucesivamente.
• \(n-r+1\) elementos para la última posición.
Como se han de realizar todas las elecciones de manera sucesiva (se elige el primero, luego el segundo, el tercero…) la cantidad total de variaciones que pueden realizarse está dada por el producto factorial truncado:
$$V_n^r=n\left(n-1\right)\left(n-2\right)\left(n-3\right)\cdots\left(n-r+1\right)$$
A través de procedimientos algebraicos, es posible reescribir la expresión como:
$$V_n^r=\frac{n\left(n-1\right)\left(n-2\right)\left(n-3\right)\cdots\left(n-r+1\right) \textcolor{#ff0080}{\left(n-r\right)\left(n-r-1\right)\cdots2(1)}}{\left(n-r\right)\left(n-r-1\right)\cdots2(1)}$$
donde la expresión
$$\left(n-r\right)\left(n-r-1\right)\cdots2(1)=(n-r)!$$
es introducida en la fórmula con la finalidad de tener \(n!\) en el numerador de la expresión, con lo cual \(V_n^r\) se resume en la forma:
Variación de \(n\) elementos
Nota: por lo general, la notación en español para variaciones es \(V_n^r ~~{\rm o}~~ nVr\). El uso de la forma \(nPr\) proviene del inglés permutations y se adopta solo para la uniformidad de la notación con calculadora y dispositivos electrónicos (no es una obligación).
Ver Ejercicio I Ej8 al Ejercicio II Ej1.
Variaciones con repetición.
Se llaman variaciones con repetición de \(n\) elementos tomados de \(r\) en \(r\) las cuales denotaremos como \({VR}_n^r\) a los distintos grupos formados por \(r\) elementos tales que,
• \(r\) no depende de tamño de \(n\). Si \(r>n\) obliga a repetir elementos.
• Importa el orden.
• Se repiten elementos.
Variaciones con repetición de \(n\) elementos
Ver Ejercicios II, Ej2, Ej3 y Ej4
Para más contenidos y luego clic en la pestaña del contenido deseado.
Combinaciones ordinarias.
Se llama combinaciones de \(n\) elementos tomados de \(r\) en \(r\) donde \(n\geq r\), denotadas como \(C_n^r=nCr\), a todas las agrupaciones posibles que pueden hacerse tales que,
• Pueden entrar o no todos los elementos.
• No importa el orden.
• No se repiten los elementos.
Ya se demostró que, para el caso de una variación sin repetición, la cantidad total de arreglos posibles está dada por la expresión:
$$V_n^r=\frac{n!}{\left(n-r\right)!}$$
En una variación sin repetición los distintos arreglos que pueden formarse con un grupo de \(r\) elementos han sido contados \(r!\) veces. Como las combinaciones no consideran el orden de los elementos, al suprimir esta condición, es necesario dividir la expresión para la variación entre la cantidad \(r!\), de donde se obtiene:
Combinaciones de \(n\) elementos sin repetición
$$nCr=\left(\begin{matrix}n\\r\\\end{matrix}\right)=\frac{n!}{r!\left(n-r\right)!}$$
Número combinatorio.
Dado un conjunto no vacío de \(n\) elementos, se dice que el número combinatorio es el número de combinaciones ordinarias de los subgrupos de \(r\) dados por la expresión anterior.
Ver el apartado Ejercicios II los ejemplos Ej5 al Ej7.
Combinaciones con repetición.
Llamaremos combinaciones con repetición de \(n\) elementos tomados de \(r\) en \(r\), lo cual denotaremos como \({CR}_n^r\), a los distintos grupos formados por \(r\) elementos tales que,
•Pueden o no entrar todos los elementos si \(n\le r\).
•No importa el orden.
•Se pueden repetir los elementos.
Combinación con repeticón de \(n\) elementos de \(r\) en \(r\)
$$C_n^r=\left(\begin{matrix}n+r-1\\r\\\end{matrix}\right)=\frac{(n+r-1)!}{r!\left(n-1\right)!}$$
Ver el apartado Ejercicios II los ejemplos Ej8 al Ej10.
Para más contenidos y luego clic en la pestaña del contenido deseado.
Una clave alfanumérica. ¿De cuántas maneras diferentes es posible crear una clave alfanumérica con los caracteres \(123ABC\), usando cada carácter una sola vez?
Una carrera de atletismo. ¿De cuántas formas distintas pueden llegar los ocho corredores de una carrea de atletismo? Si el ganador de la carrera es fijo como cambia el resultado.
Jugando con números. Determinar cuántas claves distintas, se pueden hacer con los caracteres \(0,0,0,0,1,1,1,2,2\) usando cada carácter.
Jugando con números. Cuántos claves numéricas de diez dígitos, se pueden escribir con las cifras \(2, 2, 2, 2, 3, 3, 3, 5, 5, 5\)
Arreglos de colores. Una cesta contiene tres bolas rojas, cinco bolas verdes y tres bolas azules. ¿Cuántas arreglos diferentes se pueden hacer con las onces bolas?
Arreglo de números. Determinar todos los números de dos dígitos que se pueden escribir con los dígitos 1, 2, 3, 4, 5. Sin repetir un dígito.
Arreglos de números. ¿Cuántos números cualquieras, de tres cifras diferentes se pueden formar con los dígitos 0, 2, 4 y 5?
Un ejercicio interesante. ¿Cuántos números naturales de tres cifras se pueden formar con los dígitos 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 sin repetir un dígito?
Dos soluciones identicas en contextos distintos.
a. Clave telefónica De cuanta maneras diferentes una persona puede elegir una clave numérica de seis dígitos para su teléfono.
b. Determinar cuántas matrículas de automóviles de forma Axxxxxx se pueden formar con los dígitos del 0 al 9, donde x representa un dígito cualquiera.
Número telefónico. Determine cuantos números telefónicos en la forma 809-528-xxxx se pueden formar con los dígitos del cero al nueve. Explique que pasaría para el número 10 001 en esta forma.
Comité de personas. Determinar cuántos comités de cuatro personas se pueden formar con un grupo de seis personas.
Puntos sobre una circunferencia. Sobre una circunferencia se marcan seis puntos equidistantes. Al unir los puntos tres a tres mediante segmentos de rectas ¿Cuántos triángulos quedan determinados?
Epístolas paulinas. Como parte de la formación eclesiástica, se desea armar un grupo de estudio para los próximos tres meses, seleccionando tres cartas paulinas distintas de las trece existentes. ¿De cuántas formas posibles se puede realizar esto, si no importa el orden?
Elección de vinos. Una bodega contiene seis tipos de vinos. De cuanta maneras se pueden elegir cuatro botellas de vino de ella, si se pueden elegir tantas botellas como se desee de cada tipo?
juagando a la lotería. En algunos juego de lotería los números suelen ir desde el 01, 02, 03… hasta 100. Se denomina palé a un arreglo de dos números cualquiera en el cual no importa el orden y se puede repetir un número. Determinar cuántos palés se pueden tener con los números del 01, 02, 03… hasta 100.